﻿// Copyright (c) 2009, Heiko Wundram (modelnine@h8me.eu).
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following
// conditions are met:
//
// * Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer
//   in the documentation and/or other materials provided with the distribution.
// * Neither the name of Heiko Wundram (h8me.eu) nor the names of its contributors may be used to endorse or promote products
//   derived from this software without specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING,
// BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT
// SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
// INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
// NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

using System;
using System.Collections.Generic;
using System.IO;
using System.Text;
using eu.h8me.Parsing.ParserLib;

namespace eu.h8me.Parsing.LexerLib {

    // Lexer implementation class.
    public sealed class Lexer {

        // Constants.
        private const int BUFFER_SIZE = 128;

        // Data.
        private RegExSet _Set;
        private Stack<RegExSetState> _StateStack = new Stack<RegExSetState>();
        private HashSet<RegExSetState> _EOISignalled = new HashSet<RegExSetState>();
        private object _Tag;
        private StreamReader _Input;
        private Dictionary<RegEx, int> _Matches = new Dictionary<RegEx, int>();
        private StringBuilder _Buffer = new StringBuilder(BUFFER_SIZE);
        private int _Processed;
        private bool _Started;
        private bool _AtNewLine = true;

        // Constructor.
        internal Lexer(RegExSet set) {
            // Store data; initializing with default state.
            _Set = set;
            _StateStack.Push(set);
        }

        // Tag.
        public object Tag {
            get {
                // Fetch tag.
                return _Tag;
            }
            set {
                // Set up tag.
                if( _Started )
                    throw new ArgumentException("Trying to set lexer tag after start");
                _Tag = value;
            }
        }

        // Access started flag.
        public bool Started {
            get {
                // Return started flag.
                return _Started;
            }
        }

        // Access EOI flag.
        public bool EOI {
            get {
                // Return EOI flag.
                return _EOISignalled.Count > 0;
            }
        }

        // Push a state.
        public void PushState(string state) {
            // Check what to push.
            if( !_Started )
                throw new ArgumentException("Trying to push state when not started");
            else if( state == null )
                // Push base state.
                _StateStack.Push(_Set);
            else
                // Push named state.
                _StateStack.Push(_Set[state]);
        }

        // Pop a state.
        public void PopState() {
            // Pop pending state.
            if( !_Started )
                throw new ArgumentException("Trying to pop state when not started");
            else if( _StateStack.Count == 1 )
                throw new ArgumentException("Trying to pop last state from state stack");
            _StateStack.Pop();
        }

        // Lexing callback for string.
        public Parser.LexerCallback Lex(string data) {
            // Check data.
            if( data == null )
                throw new ArgumentNullException("Trying to start lexer with NULL data");

            // Use memory stream of encoded bytes.
            Encoding enc = new UTF8Encoding();
            return Lex(new MemoryStream(enc.GetBytes(data)), enc, false);
        }

        // Lexing callback with default encoding.
        public Parser.LexerCallback Lex(Stream input) {
            // Use standard values.
            return Lex(input, new ASCIIEncoding(), false);
        }

        // Lexing callback.
        public Parser.LexerCallback Lex(Stream input, Encoding enc, bool detectbom) {
            // Check state and data.
            if( input == null || enc == null )
                throw new ArgumentNullException("Trying to start lexer with NULL input or encoding");
            else if( _Started )
                throw new ArgumentException("Trying to start lexer when already started");
            _Started = true;

            // Initialize state and return delegate.
            _Input = new StreamReader(input, enc, detectbom, BUFFER_SIZE);
            return LexerCallback;
        }

        // Lexer callback.
        internal Token LexerCallback(Grammar gram, Parser parser) {
            while( _EOISignalled.Count == 0 ) {
                // Initialize state and position on call entry.
                RegExSetState curstate = _StateStack.Peek();
                int state = curstate.StartState;
                int pos = 0;

                // Fetch input tokens while there are transitions.
                int curmatchpos = 0;
                RegEx curmatchre = null;
                bool found;
                do {
                    // Check whether current character is an accepting state.
                    AcceptorSet matchset = curstate.Acceptors[state];
                    RegEx matchre = _AtNewLine ? matchset.NewlineAcceptor : matchset.Acceptor;

                    // Check whether we have a match.
                    if( matchre != null ) {
                        // Yes, there is a match; check whether we've had a match of this RE ending at this position before.
                        // If so, don't match it (which avoids an endless loop matching epsilon).
                        int lastmatchpos;
                        if( !_Matches.TryGetValue(matchre, out lastmatchpos) || _Processed + pos > lastmatchpos ) {
                            // Set up match.
                            curmatchpos = pos;
                            curmatchre = matchre;
                        }
                    }

                    // Check whether we can have more matches.
                    if( pos == _Buffer.Length ) {
                        // Fetch some data from input stream to buffer.
                        char[] buf = new char[BUFFER_SIZE];
                        int read = _Input.Read(buf, 0, buf.Length);

                        // Check whether data was read. In case no data was read, this is EOI.
                        if( read == 0 )
                            break;
                        _Buffer.Append(buf, 0, read);
                    }

                    // Fetch character and transitions, and walk ahead in input.
                    char c = _Buffer[pos++];
                    found = false;
                    foreach( DFATransition trans in curstate.TransitionSet[state] ) {
                        // Check whether the range matches.
                        if( trans.Range.Start > c )
                            // No transition possible; out of range.
                            break;
                        else if( trans.Range.Stop < c )
                            // Transition possibly comes later.
                            continue;

                        // Found a transition. Update state with new transition.
                        found = true;
                        state = trans.Destination;
                        break;
                    }
                } while( found );

                // Check match re.
                if( curmatchre == null ) {
                    // This is only an error in case there is actually a buffer; in case the buffer is empty, this is total EOI.
                    if( _Buffer.Length > 0 )
                        throw new ArgumentException("Lexer jammed, no more possible transitions");
                    break;
                }

                // Extract matched data from buffer (updating it to remove data, and reset the newline indicator).
                string match = _Buffer.ToString().Substring(0, curmatchpos);
                _AtNewLine = match.Length > 0 ? match[match.Length - 1] == '\n' : _AtNewLine;
                _Buffer.Remove(0, curmatchpos);

                // Execute match re on buffer and record match in positioning.
                Token tok = curmatchre.Execute(_Set, gram, curstate, this, parser, _Processed, match);
                _Processed += curmatchpos;
                _Matches[curmatchre] = _Processed;

                // Return token if valid.
                if( tok != null )
                    return tok;
            }

            // Set up EOI state when we get here.
            while( true ) {
                // Check current state whether we've already executed the EOI event.
                RegExSetState curstate = _StateStack.Peek();
                if( _EOISignalled.Contains(curstate) )
                    break;
                _EOISignalled.Add(curstate);

                // Execute action of current state.
                Token tok = curstate.EOIExecute(_Set, gram, this, parser, _Processed);
                if( tok != null )
                    return tok;
            }

            // Return grammar EOI.
            return gram.EOI;
        }

    }

    // Helper class for an acceptor set.
    internal class AcceptorSet {

        // Data.
        private RegEx _NewlineAcceptor;
        private RegEx _Acceptor;
        private int? _Hash;

        // Constructor.
        public AcceptorSet() {
            // No specific construction.
        }

        // Access newline acceptor.
        public RegEx NewlineAcceptor {
            get {
                // Return newline acceptor.
                return _NewlineAcceptor;
            }
        }

        // Access "normal" acceptor.
        public RegEx Acceptor {
            get {
                // Return normal acceptor.
                return _Acceptor;
            }
        }

        // Adding item to acceptor set.
        public void Add(RegEx re) {
            // Only attach this as acceptor in case it doesn't require newline matching.
            if( !re.MatchAtNewLine && ( _Acceptor == null || _Acceptor.Precedence < re.Precedence ) )
                _Acceptor = re;

            // Compare against newline acceptor.
            if( _NewlineAcceptor == null || _NewlineAcceptor.Precedence < re.Precedence )
                _NewlineAcceptor = re;
        }

        // Hashing.
        public override int GetHashCode() {
            // Check whether hash code has been calculated.
            if( !_Hash.HasValue ) {
                // Build hash from contents.
                int hash = _NewlineAcceptor != null ? _NewlineAcceptor.GetHashCode() : 0;
                hash = ( ( hash << 16 ) | ( hash >> 16 ) ) ^ ( _Acceptor != null ? _Acceptor.GetHashCode() : 0 );

                // Store hash.
                _Hash = hash;
            }

            // Return hash.
            return _Hash.Value;
        }

        // Equivalence testing.
        public override bool Equals(object obj) {
            // Cast to type and compare contents.
            AcceptorSet other = obj as AcceptorSet;
            return other != null && other._NewlineAcceptor == _NewlineAcceptor && other._Acceptor == _Acceptor;
        }

    }

    // Helper class for a DFA transition.
    internal class DFATransition {

        // Data.
        private Range _Range;
        private int _Destination;

        // Constructor.
        public DFATransition(Range range, int dest) {
            // Store data.
            _Range = range;
            _Destination = dest;
        }

        // Access contained range.
        public Range Range {
            get {
                // Return range.
                return _Range;
            }
        }

        // Access contained destination.
        public int Destination {
            get {
                // Return destination.
                return _Destination;
            }
        }

    }

}
